Let a and b be any two integers, not both equal to 0, and consider the set of all positive integers which divide both a and b. Let d be the greatest of this set of common divisors. The integer d is called the greatest common divisor of a and b, and written d = (a,b).
A short and certain method for calculating the GCD is provided by the Euclidean algorithm. It is based on the fact that from any relation of the form:
It follows that
For any number u which divides both a and b,
also divides r, since
And conversely, every number v which divides b and r, also divides a (by the same reasoning). Hence every divisor of a and b is at the same time a common divisor of b and r, and conversely. Since, therefore, the set of all common divisors of a and b is identical with the set of all common divisors of b and r, the greatest common divisor of a and b must be equal to the greatest common divisor of b and r.
As an example let's find the GCD of 1804 and 328. By ordinary long division
Therefore we can conclude that
The problem of finding the GCD of 1804 and 328 has been reduced to finding the GCD of 328 and 164. This can be continued by dividing 328 by 164:
So the GCD of 328 and 164 is the same as the GCD of 164 and 0, which is 164. Consequently, the GCD of 1804 and 328 is 164. This is the essence of the Euclidean algorithm.
The calculator returns the Greatest common divisor for any two selected numbers using the Euclidean algorithm demonstrated above. To use the calculator simply enter the two numbers. Then hit the button to calculate the list.